package qjc.g_链表;

import com.链表.练习题.ListNode;

import java.awt.desktop.PreferencesEvent;
import java.util.HashMap;
import java.util.HashSet;

public class g14_LRU缓存 {
    static class Node {
        int value;
        int key;
        Node pre;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class DoublyLinkedList {
        private final Node head;
        private final Node tail;

        DoublyLinkedList() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        void addFirst(Node newNode) {
            Node oldNode = head.next;
            newNode.pre = head;
            newNode.next = oldNode;
            head.next = newNode;
            oldNode.pre = newNode;
        }

        void remove(Node node) {
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            node.pre = null;
            node.next = null;
        }

        Node removeLast() {
            if (head.next == null) {
                return null;
            }
            Node last = tail.pre;
            remove(last);
            return last;
        }
    }

    private HashMap<Integer, Node> map = new HashMap<>();
    private DoublyLinkedList linkedList = new DoublyLinkedList();
    private int capacity = 0;

    public g14_LRU缓存(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        linkedList.remove(node);
        linkedList.addFirst(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            linkedList.remove(node);
            linkedList.addFirst(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            linkedList.addFirst(node);
            if (map.size() > capacity) {
                Node last = linkedList.removeLast();
                if (last != null) {
                    map.remove(last.key);
                }
            }
        }
    }
}
